//任选m个下标I[0]......I[m-1],2^(I[j])中恰有k个1 f(I)=nums[I[j]]的累乘->一个下标选择了几次，再对每一位作组合运算
//f(I)=累乘(nums[i])^ci 枚举ci

const int N=31; //阶乘最大长度
class Solution {
public:
    using ll=long long;

    const ll MOD=1e9+7; ll mod(ll x) {return (x%MOD+MOD)%MOD;}
    ll qmi(ll base, ll index)
    {
        ll res=1;
        while(index)
        {
            if(index&1) res=mod(res+base);
            base=mod(base*base);
            index>>=1;
        }
        return res;
    }

    ll Jie[N], invJie[N]; //i!,(i!)^-1

    void init()
    {
        Jie[0]=1;
        for(int i=1; i<N; i++) Jie[i]=mod(Jie[i-1]*i);
        invJie[N-1]=qmi(Jie[N-1], MOD-2);
        for(int i=N-1; i; i--) invJie[i-1]=mod(invJie[i]*i);
    }
    
    //i当前考虑nums的第i个数 left_m:剩余可选的元素总数 x:S的最高位部分(S>>i)的进位 left_k:S的二进制表示中还需要的1的个数
    ll dfs(vector<vector<ll>> &numsPower, vector<vector<vector<vector<int>>>> &memo, int n, int i, int left_m, int x, int left_k)
    {
        int count1=popcount((uint32_t) x);
        //如果当前进位中1的个数+剩余可选元素总数还小于需要的->不可能凑够left_k个1
        if(count1+left_m<left_k) return 0; //可行性剪枝
        //递归出口：所有数字全被考虑||没有可选的||不需要1
        if(i==n||left_m==0||left_k==0) return left_m==0&&count1==left_k;

        int &res=memo[i][left_m][x][left_k];
        if(res!=-1) return res; //记忆化搜送
        res=0; //标记在搜索中
        for(int j=0; j<=left_m; j++) { //枚举I中有j个下标i
            //j个下标i对S的贡献是j*qmi(2, i)
            //由于x=S>>i,转化成对x的贡献是j
            int bit=(x+j)&1; //取最低位，提前从left_k中减去，其余进位到x中
            //r是子问题的解
            ll r=dfs(numsPower, memo, n, i+1, left_m-j, (x+j)>>1, left_k-bit);

            res=mod(res+1ll*mod(r*numsPower[i][j])*invJie[j]);
        }
        return mod(res);
    }

    int magicalSum(int m, int k, vector<int>& nums) { //seq[i]组成的二进制串共有k个`
        int n=nums.size();
        init();
        vector numsPower(n, vector<ll>(m+1)); //预处理nums中每个数的幂，numsPower[i][j]=qmi(nums[i], j)
        for(int i=0; i<n; i++) {
            numsPower[i][0]=1;
            for(int j=1; j<=m; j++) numsPower[i][j]=mod(1ll*numsPower[i][j-1]*nums[i]);
        }
        vector memo(n, vector(m+1, vector(m/2+1, vector<int>(k+1, -1))));
        return mod(1ll*dfs(numsPower, memo, n, 0, m, 0, k)*Jie[m]);
    }
};